Moving average from data stream

Time: O(1); Space: O(W); easy

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Have you met this question in a real interview?

Example 1:

Input:

m = new MovingAverage(3)
m.next(1)  => 1                # return 1.00000
m.next(10) => (1 + 10) / 2     # return 5.50000
m.next(3)  => (1 + 10 + 3) / 3 # return 4.66667
m.next(5)  => (10 + 3 + 5) / 3 # return 6.00000

[5]:

from collections import deque

class MovingAverage(object):
    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.__size = size
        self.__sum = 0
        self.__q = deque()

    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        if len(self.__q) == self.__size:
            self.__sum -= self.__q.popleft()
        self.__sum += val
        self.__q.append(val)
        return 1.0 * self.__sum / len(self.__q)

[8]:

m = MovingAverage(3)
assert m.next(1)  == 1.0   #  1,                return 1.00000
assert m.next(10) == 5.5  # (1 + 10) / 2,      return 5.50000
assert m.next(3)  == 4.666666666666667  # (1 + 10 + 3) / 3,  return 4.66667
assert m.next(5)  == 6.0   # (10 + 3 + 5) / 3,  return 6.00000